This invention relates to a method and apparatus for division in a digital computation. This invention is particularly useful for implementing the power series to an electronic digital computer system.
Heretofore, it has been suggested to implement a multiplication method to division process. One technique described in "The IBM System/360 Model 91: Floating-Point Execution Unit" IBM Journal of Res. & Develop. Vol. 11 No. 1, 1967 pp. 34-54 by S. F. Anderson et al. suggests that a succession of factor multiplications to the dividend and divisor leads to the results; an approximated quotient and one, respectively. The selection of the multiplying constant a.sub.k is the essential part of the procedure. This procedure is shown: EQU A/B=Aa.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 a.sub.5 . . . /Ba.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 a.sub.5 . . .
Aa.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 . . . a.sub.n is an approximated quotient, when Ba.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 . . . a.sub.n is approaching to one. The divisor can be expressed as C=1-x where x.ltoreq.1/2, since C is a bit-normalized, binary floating-point fraction of the form 0.1yyy . . . . Now, if the constant a.sub.0 is set equal to 1+x and the divisor is multiplied by a.sub.0, then C.sub.1 =Ca.sub.0 =(1-x).multidot.(1+x)=1-x.sup.2 where x.sup.2 .ltoreq.1/4. The new divisor is guaranteed to have the form 0.11yyy . . . . Likewise, select a.sub.1 =1+x.sup.2 with double the leading 1 on the next iteration to yield C.sub.2 =C.sub.1 a.sub.1 =(1-x.sup.2).multidot.(1+x.sup.2)=1-x.sup.4 where x.sup.4 .ltoreq.1/16. In general, if x.sub.i .ltoreq.(1/2).sup.n then x.sub.i+1 .ltoreq.(1/2).sup.2n. Thus, by continuing the multiplication until x.sub.i is less than the least significant digit (bit) of the divisor (division fraction), the desired result, namely a denominator (a constant multiplied divisor) equivalent to one (=0.111 . . . 111 . . . ) is obtained. The multiplier a.sub.i for each succession is the two's complement of the denominator a.sub.i =2-a.sub.i-1 =2-(1-x.sub.i-1)=1+x.sub.i-1.
The first multiplier a.sub.0 is generated by a table-lookup which inspects the first seven bits of the divisor. The first multiply guarantees a result which has seven similar bits to the right of the binary point (1+x has the form b.bbbbbbb . . . etc.) where b is the negated number of b. The following sequence outlines the operations: (1) determine the first multiplier by a table-lookup, (2) multiply B by a.sub.0 forming B.sub.1, (3) multiply A by a.sub.0 forming A.sub.1, (4) truncate B.sub.i and complement to form a.sub.i, (5) multiply A.sub.i by a.sub.i forming A.sub.i+1, (6) multiply B.sub.i by a.sub.i forming B.sub.i+1, (7) iterate on (4), (5), and (6) until B.sub.i+n approaches one and then A.sub.i+n becomes an approximated quotient of the division A/B.
It is one object of the present invention to provide a method and apparatus for performing division A/B.
It is another object to accomplish a division process quickly by evaluating a power series.
Other objects and features of the present invention will be apparent in view of the following general and specific descriptions of embodiments of the invention.